Balancing networks are highly distributed data structures used to solve multiprocessor synchronization problems. Typically, balancing networks are accessed by tokens, and the distribution of the tokens on the network’s ...

The possibility or impossibility and the corresponding costs of devising concurrent, low-contention implementations of atomic Read&Modify&Write (or RMW) operations in a distributed system were addressed. A natural class ...

Direct routing is the special case of bufferless routing where N packets, once injected into the network, must be routed along specific paths to their destinations without conflicts. We give a general treatment of three ...

Counting networks were introduced as a new class of concurrent, distributed, low contention data structures suitable for implementing shared counters. Their structure is similar to that of sorting networks. High-performance ...

It is shown that a weak threshold network (in particular, threshold network) of width w and depth d cannot be constructed from balancers of width p0, p1, . . . , pm-1, if w does not divide Pd, where P is the least common ...

This paper shows that any counting network, made up of balancers whose fan-in and fan-out vary arbitrarily, is, indeed, strong enough to simultaneously support both Fetch&Increment and Fetch&Decrement operations, once each ...

A threshold counter is a shared data structure that assumes integer values. It provides two operations: Increment changes the current counter value from v to v+1, while Read returns the value [v/w], where v is the current ...

Given an arbitrary network, and a routing problem with congestion C and dilation D, a long standing open problem is to show the existence of bufferless routing algorithms with optimal performance guarantees (routing time ...